/* ==========================================
 * JGraphT : a free Java graph-theory library
 * ==========================================
 *
 * Project Info:  http://jgrapht.sourceforge.net/
 * Project Creator:  Barak Naveh (http://sourceforge.net/users/barak_naveh)
 *
 * (C) Copyright 2003-2006, by Barak Naveh and Contributors.
 *
 * This library is free software; you can redistribute it and/or modify it
 * under the terms of the GNU Lesser General Public License as published by
 * the Free Software Foundation; either version 2.1 of the License, or
 * (at your option) any later version.
 *
 * This library is distributed in the hope that it will be useful, but
 * WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
 * or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public
 * License for more details.
 *
 * You should have received a copy of the GNU Lesser General Public License
 * along with this library; if not, write to the Free Software Foundation,
 * Inc.,
 * 59 Temple Place, Suite 330, Boston, MA 02111-1307, USA.
 */
/* -----------------
 * IsomorphismRelation.java
 * -----------------
 * (C) Copyright 2005-2006, by Assaf Lehr and Contributors.
 *
 * Original Author:  Assaf Lehr
 * Contributor(s):   -
 *
 * $Id: IsomorphismRelation.java,v 1.2 2007/05/22 15:52:55 kjellw Exp $
 *
 * Changes
 * -------
 */
package org.jgrapht.experimental.isomorphism;

import java.util.*;

import org.jgrapht.*;
import org.jgrapht.graph.*;

/**
 * Holds an isomorphism relation for two graphs. It contains a mapping between
 * the two graphs.
 * 
 * <p>
 * Usage:
 * 
 * <ol>
 * <li>use <code>getVertexCorrespondence()</code> or <code>
 * getEdgeCorrespondence()</code>
 * to get the mapped object in the other graph.
 * </ol>
 * 
 * <p>
 * <p>
 * It consists of two vertexes array , the i-th vertex in the 1st array is the
 * isomorphic eqv. of the i-th in 2nd array. Note that the getters are unsafe
 * (they return the array and not a copy of it).
 * 
 * @author Assaf
 * @since May 27, 2005
 */
public class IsomorphismRelation<V, E> implements GraphMapping<V, E> {
	// ~ Instance fields
	// --------------------------------------------------------

	private List<V> vertexList1;

	private List<V> vertexList2;

	private GraphMapping<V, E> graphMapping = null;

	private Graph<V, E> graph1;

	private Graph<V, E> graph2;

	// ~ Constructors
	// -----------------------------------------------------------

	/**
	 */
	public IsomorphismRelation(List<V> aGraph1vertexArray,
			List<V> aGraph2vertexArray, Graph<V, E> g1, Graph<V, E> g2) {
		this.vertexList1 = aGraph1vertexArray;
		this.vertexList2 = aGraph2vertexArray;
		this.graph1 = g1;
		this.graph2 = g2;
	}

	// ~ Methods
	// ----------------------------------------------------------------

	public String toString() {
		StringBuffer sb = new StringBuffer();
		sb.append("vertexList1: ").append(this.vertexList1.toString());
		sb.append("\tvertexList2: ").append(this.vertexList2.toString());
		return sb.toString();
	}

	public V getVertexCorrespondence(V vertex, boolean forward) {
		// lazy initializer for graphMapping
		if (graphMapping == null) {
			initGraphMapping();
		}

		return graphMapping.getVertexCorrespondence(vertex, forward);
	}

	public E getEdgeCorrespondence(E edge, boolean forward) {
		// lazy initializer for graphMapping
		if (graphMapping == null) {
			initGraphMapping();
		}

		return graphMapping.getEdgeCorrespondence(edge, forward);
	}

	/**
	 * We currently have the vertexes array. From them we will construct two
	 * maps: g1ToG2 and g2ToG1, using the array elements with the same index.
	 */
	private void initGraphMapping() {
		int mapSize = vertexList1.size();
		Map<V, V> g1ToG2 = new HashMap<V, V>(mapSize);
		Map<V, V> g2ToG1 = new HashMap<V, V>(mapSize);

		for (int i = 0; i < mapSize; i++) {
			V source = this.vertexList1.get(i);
			V target = this.vertexList2.get(i);
			g1ToG2.put(source, target);
			g2ToG1.put(target, source);
		}
		this.graphMapping = new DefaultGraphMapping<V, E>(g1ToG2, g2ToG1,
				this.graph1, this.graph2);
	}
}

// End IsomorphismRelation.java
